package Algorithm.DivideAndConquer;

//分治算法 解决 汉诺塔问题
public class HanoiTower {
	public static void main(String[] args) {
		hanoitower(4, 'A', 'B', 'C');
		System.out.println(line);
	}

	/**
	 * 汉诺塔的移动
	 *
	 * @param num 圆盘个数
	 * @param a 第一根柱子
	 * @param b 第二根柱子
	 * @param c 第三根柱子
	 */
	static int line = 0;

	public static void hanoitower(int num, char a, char b, char c) {

		//如果只有一个盘
		if (num == 1) {
			System.out.println("第1个盘从 " + a + "->" + c);
			line++;
		} else {
			// 1. 先把上面的盘 A->B,移动过程会使用到c
			hanoitower(num - 1, a, c, b);
			// 2. 把最下面一个盘 A->C
			System.out.println("第" + num + "个盘从 " + a + "->" + c);
			line++;
			// 3. 把B上的所有盘从B->C，移动过程会使用到A
			hanoitower(num - 1, b, a, c);
		}
	}
}
